from collections import Counter

# 旅途规划问题

# 城市类 - 表示一个城市信息
# 这个类同时用作双向链表的节点，用于维护作为插入排序使用的队列链表
class City:
    def __init__(self, name: str) -> None:
        # 名称（标识）
        self.name = name
        # 从该城市出发的相邻路径(用链表存储)
        self.head = None
        # 从起点出发到该城市的总票价（总路径长度）
        self.amount = -1 
        # 双向链表的前后指针
        self.prev, self.next = None, None

# 航班类（表示一条路径）
class Trip:
    def __init__(self, s: City, t: City, p: int) -> None:
        # 航班起点、终点
        self.start, self.end = s, t
        # 航班票价（边权重，或称路径长度）
        self.price = p
        # 单指针
        self.next = None

class TripPlanSolution:
    def __init__(self) -> None:
        # 维护所有城市列表
        self.cities = {}

    # 从列表获取城市，如果不在列表中则新建一个并添加
    def getCity(self, name: str) -> City:
        if name in self.cities:
            return self.cities[name]
        else:
            c = City(name)
            self.cities[name] = c
            return c

    # 添加航班（有向边）
    def addTrip(self, start: str, end: str, price: int):
        startCity, endCity = self.getCity(start), self.getCity(end)
        trip = Trip(startCity, endCity, price)
        # 使用头插法把航班添加到起点城市的邻接表中
        trip.next = startCity.head
        startCity.head = trip

    ## 用Dijkstra计算（不超预算的）所有航班路线
    ## src 起点城市
    ## budget 预算（即路径长度上限），超出的答案不需要返回
    ## 返回所有预算内的目标城市及最小票价
    def findAllShortestPath(self, src: str, budget: int) -> Counter:
        # 创建存放答案的容器
        answer = Counter()

        # 初始化起点信息：创建排序链表并将起点放入为第一个元素
        headCity = self.getCity(src)
        headCity.amount = 0

        # 执行dijkstra搜索最短路径
        while headCity:
            # 取出头节点作为当前节点，输出到答案
            s = headCity
            headCity = headCity.next
            answer[s.name] = s.amount

            # 枚举当前城市的邻接路径，发现新的路径并更新维护排序数组
            trip = s.head
            while trip:
                # 当前路径的目标点为t，当前总路径长度=起点到s长度+s到t的长度
                t = trip.end
                newAmount = s.amount + trip.price
                trip = trip.next

                # 题目要求：不考虑超出预算的航线
                if newAmount > budget: 
                    continue 

                # 情形1: 该相邻点第一次访问，使用插入排序加入队列
                if t.amount == -1:
                    # 计算当前搜索到的路径长度（权值）
                    t.amount = newAmount
                    # 使用头插法插入排序将该顶点加入队列
                    if not headCity or t.amount <= headCity.amount:
                        if headCity:
                            t.next = headCity
                            headCity.prev = t
                        headCity = t
                    else:
                        c = headCity
                        while c.next and c.next.amount < t.amount:
                            c = c.next
                        t.next = c.next
                        if c.next: 
                            c.next.prev = t
                        c.next = t
                        t.prev = c
                # 情形2: t 之前被搜索到，且当前路径需要更新
                elif newAmount < t.amount:
                    # 更新旅途费用
                    t.amount = newAmount

                    # 定位到新的排序位置
                    c = t
                    while c != headCity and c.prev.amount > t.amount: 
                        c = c.prev

                    # 执行链表位置交换
                    if t != c:
                        # 先将t从链表移除
                        t.prev.next = t.next
                        if t.next:
                            t.next.prev = t.prev
                        # 再将t插入链表（替换c的位置）
                        if c == headCity:
                            headCity.prev = t
                            t.next = headCity
                            headCity = t
                        else:
                            t.prev = c.prev
                            if t.prev:
                                t.prev.next = t
                            t.next = c
                            c.prev = t
        # 返回最终结果
        return answer
    
# main
sln = TripPlanSolution()
sln.addTrip('广州', '长沙', 200)
sln.addTrip('广州', '北京', 800)
sln.addTrip('广州', '上海', 300)
sln.addTrip('长沙', '武汉', 500)
sln.addTrip('武汉', '北京', 100)
sln.addTrip('上海', '武汉', 200)
sln.addTrip('上海', '北京', 600)
src, budget = '广州', 500
hm = sln.findAllShortestPath(src, budget)
n = len(hm)
print('从', src, '出发, 预算', budget, '元, 共有以下', n, '个方案:')
for k, c in hm.items():
    print('到', k, ' 共', c, '元')
